#!/usr/bin/env python

# ----------------------------------
# projects/python/collatz/Collatz.py
# Copyright (C) 2010
# Glenn P. Downing
# ----------------------------------

size = 10001
cache = [0]*size

# ------------
# collatz_read
# ------------

def collatz_read (r, a) :
    """
    reads an int into a[0] and a[1]
    return true if that succeeds, false otherwise
    """
    try :
        s = r.read()
    except EOFError :
        return False
    assert type(s) is str
    l = s.split()
    assert type(l) is list
    a[0:] = [int(l[0])]
    a[1:] = [int(l[1])]
    assert a[0] > 0
    assert a[1] > 0
    return True

# ------------
# collatz_eval
# ------------

def collatz_eval (a) :
    """
    computes the max cycle length in the range [i, j]
    and stores the result in v
    """
    assert a[0] > 0
    assert a[1] > 0	
    upper = a[0]
    lower = a[1]
    if upper < lower:
        tmp = lower
        lower = upper
        upper = tmp
    assert upper >= lower  
    assert upper < size
    assert lower > 0
    tmp = lower
    Max = 0;
    while (tmp < upper):
        cacheCycLen(tmp)
        tmp += 1      
  
    Max = myMax(cache, lower, upper);
    return Max

#
# myMax
#  finds the max value between two indices.
#
def myMax( cache, i, j) :
	mMax = 0
	while (i <= j):		
		if cache[i] > mMax:
			mMax = cache[i]
		i += 1
	return mMax


#
# cacheCycLen
#    fills the cache with the cycle lengths of the indexes
#    does this recursively
#    
def cacheCycLen( n):  
    if n == 1:
        cache[n] = 1
        return 1				
    elif n< size and cache [n] != 0 :
        assert n < size and n > 1
        return cache[n]				
    elif n < size :
        if n % 2 ==0 :
            cache[n] = 1 + cacheCycLen (n/2)
            return cache[n]			
        else:
            cache[n] = 2 + cacheCycLen ((n+(n>>1) + 1))
            return cache[n]				
    else:
        assert n >= size					
        if (n % 2 ==0):
            return 1 + cacheCycLen(n/2)
        else:
            return 2 + cacheCycLen((n+(n>>1) + 1))
			 	
# -------------
# collatz_print
# -------------

def collatz_print (w, a, v) :
    """
    prints the values of a[0], a[1], and v
    """
    w.write(a, v)

